A computer compiler is used to produce object code from a source code program. An instruction scheduler is a portion of a computer compiler that is used to establish the order in which at least some of the instructions will be executed. Most computers use named storage, such as registers, to store intermediate values. Part of the job of the scheduler is the allocation of the named storage. Another part of the job of the scheduler is to rearrange the order of program instructions to make efficient use of available hardware resources.
In vector processing, it is common for a set of operations to be repeated for each element of a vector or other data structure. This set of operations is often described by a data-flow graph. For example, a data-flow graph may be used to describe all of the operations to be performed on elements of the data structure for a single iteration of a program loop. It may be necessary to execute these operations number of times during the processing of an entire stream of data (as in audio or video processing for example). Considerable effort has been applied to the efficient scheduling of program loops. Software pipelining is an approach in which the execution of one iteration of a loop is started before the previous iteration has been completed. I.e. the computation of the iterations is overlapped. This may be facilitated, for example, by moving the entry point of a loop. If the entry point is moved, one or more iterations of one or more instructions of the loop are moved outside of the main loop. This generates a prolog (instructions before the main loop) or epilog (instructions after the main loop).
In another loop optimization method, redundant speculative computations in the compilation of an inner loop are eliminated. A number of loop transformations (based on the loop inductive variable) are used in order to eliminate the redundant computations.
List scheduling is a simple way to reorder instructions with a basic block. Instructions are sorted according to priority order (e.g. instructions with the longest period first, or instructions on the critical path first). Next, every instruction is checked with respect to its data dependencies. If all predecessors are already scheduled, the candidate instruction is assigned to a cycle. Resource conflicts are then taken into account and an offset is computed to delay issue of the instructions until all required functional units are guaranteed to be free when needed. This process is iterated until all instructions are scheduled.